//
// Description: 2050. 并行课程 III
// Created by Loading on 2021/12/22.
//

#include <bits/stdc++.h>

using namespace std;

int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
    /* 拓扑排序 + BFS */
    // 图
    vector<vector<int>> graph(n);
    // 每个节点的入度
    vector<int> indegree(n);

    for (auto &v : relations) {
        graph[v[0] - 1].emplace_back(v[1] - 1);
        indegree[v[1] - 1]++;
    }

    queue<int> q;
    for (int i = 0; i < n; ++i) {
        // 入度为 0，可启动，入队列
        if (indegree[i] == 0) {
            q.emplace(i);
        }
    }

    // 启动每门课程需要花费的时间
    vector<int> cost(n);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto &v : graph[u]) {
            cost[v] = max(cost[v], cost[u] + time[u]);
            // 入度为 0，说明可以启动这门课程
            if (--indegree[v] == 0) {
                q.emplace(v);
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; ++i) {
        res = max(res, cost[i] + time[i]);
    }

    return res;
}

int main() {
    int n = 5;
    vector<vector<int>> relations = {{1, 5},
                                     {2, 5},
                                     {3, 5},
                                     {3, 4},
                                     {4, 5}};
    vector<int> time = {1, 2, 3, 4, 5};

    int res = minimumTime(n, relations, time);
    cout << res << endl;

    return 0;
}